#ifndef BINTREE_H
#define BINTREE_H

#include "main.h"

struct Tnode
{
	Tnode* left;            //lave dieta
	Tnode* right;           //prave dieta
	Tnode* parent;			//rodic
	SLseg* val;             //data
	unsigned left_count;    //kolko visi vlavo
	unsigned right_count;   //~vpravo

	Tnode ( SLseg* _segment )
	{
		left		= NULL;
		right		= NULL;
		parent		= NULL;
		val			= _segment;
		left_count	= 0;
		right_count = 0;
	}
};

//trieda binarneho stromu, sweepline si sem bude ukladat segmentiky
class CBinTree
{
public:
	Tnode* head;              

	CBinTree() 	{ head = NULL; 	}
	~CBinTree() { freetree(head); }
	void freetree(Tnode* node)
	{
		if(node->left != (Tnode*)0) freetree(node->left);
		if(node->right != (Tnode*)0) freetree(node->right);	
		remove (node, true);
	}
	void freetree()
	{
		freetree(head);
	}
	// insert vlozi uzol s datami _data, vrati pointer na pridany uzol
	Tnode* insert(SLseg* data)
	{		
		if (data == NULL) throw "NULL pointer"; 
		
		Tnode* p = new Tnode(data);
		if (p == NULL) throw "Memory allocation failure";

		if (head == NULL)
		{
			head = p;
			return p;
		}

		try { Insert( head, p ); }
		catch( char* )
		{
			delete p;
			throw;
		}
		return p;
	}
	//najde v strome
	Tnode* find(SLseg* target)
	{
		if ((target == NULL)||(head==NULL)) return (Tnode*)0;
		//return Search(head, target);
		Tnode* act = head;
		while ((act!=NULL) && (act->val != NULL) && (act->val->edge != target->edge))
		{
			if (act->val->edge < target->edge)
				act = act->right;
			if (act->val->edge > target->edge)
				act = act->left;		
		}
		return act;
	}
	// Remove() is called to delete a node from the tree
	void Remove_public( SLseg* target )
	{
		if ( target == NULL ) throw "NULL pointer";
#ifdef DEBUG
		cout << "Remove " << target->edge << endl; 
#endif
		return Remove( target);
	}
	//predchadzajuci a nasledujuci uzol
	Tnode* next	( Tnode* node )	
	{
		if (node == NULL) return (Tnode*) 0;
		 
		//najlavejsi z praveho podstromu
		if (node->right != (Tnode*) 0)
		{
			Tnode* temp = node->right;
			while (temp->left != NULL) temp = temp->left;
			return temp;
		}

		if (node->parent == (Tnode*) 0) return (Tnode*) 0;

		if (node->parent->left == node) return node->parent;

		return (Tnode*) 0; 
	}
	Tnode* prev (Tnode* node )
	{		
		if (node == NULL) return (Tnode*) 0;

		//najpravejsi z laveho podstromu
		if (node->left != (Tnode*) 0) 
		{
			Tnode* temp = node->left;
			while (temp->right != NULL) temp = temp->right;
			return temp;
		}
				
		if (node->parent == (Tnode*) 0) return (Tnode*) 0;
		
		if (node->parent->right == node) return node->parent;

		return (Tnode*) 0; 
	}	
	
private: 
	//zmaze node a ak je data flag true, zmaze aj data
	void remove( Tnode* node, bool data)
	{
		if (head == node) head = (Tnode*)0;
		if (data) delete node->val; 
		delete node;
		node = (Tnode*)0;
	}
	//sukromne pridavanie, az ked uz head je nastaveny
	void Insert(Tnode* _head, Tnode* new_node)
	{
		Tnode* p = _head;
		bool flag_continue = true;

		if (_head->left_count > 100000)
		{
			cout << "Error occured!" << endl;
			exit(1);
		}

		while (flag_continue)
		{
			//ak chceme pridavat dolava
			if (new_node->val->edge < p->val->edge) 
			{
				//pridaj dolava
				++(p->left_count);
				//vlavo neni nic
				if (p->left == NULL)
				{
					//daj tam tento uzol
					p->left = new_node;
					new_node->parent = p;
					flag_continue = false;
				}
				else
				{
					//pokracuj v strome dolava
					p = p->left;
				}
			}
			//ak chceme pridavat doprava
			else if (new_node->val->edge > p->val->edge)
			{
				//pridaj doprava
				++(p->right_count);
				//vpravo nic neni
				if ( p->right == NULL )
				{
					//daj tam uzol
					p->right = new_node;
					new_node->parent = p;
					flag_continue = false;
				}
				else
				{
					//bez dalej doprava
					p = p->right;
				}
			}
			//rovnake hodnoty 
			else
			{
				//throw "Equal values not supported";
			}
		}
	}


	// called by public Search(), finds the specified data in the tree
	Tnode* Search( Tnode* head, SLseg* target)
	{
		if (head == (Tnode*)0) return (Tnode*)0;
		if (head->left_count > 100000) return (Tnode*)0;

		bool flag_continue = true;
		Tnode* p = head;
		
		while (flag_continue)
		{
			//dolava
			if (target->edge < p->val->edge)
			{
				if (p->left == NULL) 
				{
					flag_continue = false;				
					p = NULL;					
				}
				else
					p = p->left;
			}
			else 
				if (target->edge > p->val->edge)
				{
					if ( p->right == NULL )
					{
						flag_continue = false;
						p = NULL;
					}
					else
						p = p->right;
				}
				else
					flag_continue = false;
		}

		return p;
	}

//odstrani uzol s touto hodnotou zo stromu
void Remove ( SLseg* target)
{
    bool found = false;
    if (head == NULL) return;

    Tnode* parent;
    Tnode* curr = head;

    while(curr)
    {
		if(curr->val->edge == target->edge)
        {
            found = true;
            break;
        }
        else
        {
            if(curr->val->edge < target->edge)
                curr = curr->right;
            else 
                curr = curr->left;
        }
    }
    if(!found)
    {
#ifdef DEBUG
        cout<<" Data not found! "<<endl;
#endif
        return;
    }
	parent = curr->parent;

    //jednodetny
    if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL && curr->right == NULL))
    {
		//right child
        if(curr->left == NULL && curr->right != NULL)
        {
			//head
			if (parent == NULL) 
			{
				head = curr->right;
				delete curr;
				return;
			}
            if(parent->left == curr)
            {
                parent->left = curr->right;
                delete curr;
            }
            else
            {
                parent->right = curr->right;
                delete curr;
            }
        }
        else //left child
        {
			//head
			if (parent == NULL) 
			{
				head = curr->left;
				delete curr;
				return;
			}
            if(parent->left == curr)
            {
                parent->left = curr->left;
                delete curr;
            }
            else
            {
                parent->right = curr->left;
                delete curr;
            }
        }
        return;
    }

    //list
    if( curr->left == NULL && curr->right == NULL)
    {
		if (parent == NULL) 
		{
			delete curr; 
			head = NULL;
			return;
		}
        if(parent->left == curr) parent->left = NULL;
        else parent->right = NULL;
        delete curr;
        return;
    }

	//dvojdetny, nahrad najmensim vpravo do neho
    if (curr->left != NULL && curr->right != NULL)
    {
        Tnode* chkr;
        chkr = curr->right;
        if((chkr->left == NULL) && (chkr->right == NULL))
        {
            curr = chkr;
            delete chkr;
            curr->right = NULL;
        }
		//prave dieta ma deti
        else 
        {
			//ma lave dieta, zober najvacsi uzol z toho podstromu
            if((curr->right)->left != NULL)
            {
                Tnode* lcurr;
                Tnode* lcurrp;
                lcurrp = curr->right;
                lcurr = (curr->right)->left;
                while(lcurr->left != NULL)
                {
                    lcurrp = lcurr;
                    lcurr = lcurr->left;
                }
                curr->val = lcurr->val;
                delete lcurr;
                lcurrp->left = NULL;
            }
            else
            {
                Tnode* tmp;
                tmp = curr->right;
                curr->val= tmp->val;
                curr->right = tmp->right;
                delete tmp;
            }
        }
        return;
    }
}
};
#endif
